home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Papers / C++ Exceptions / µShell / Array Classes / (Hidden) / SortedDynamicArray.cp < prev    next >
Encoding:
Text File  |  1996-01-13  |  1.5 KB  |  66 lines  |  [TEXT/CWIE]
  1. /*
  2.     File:        SortedDynamicArray.cp
  3.  
  4.     Contains:    An abstract base class for sorted dynamic arrays
  5.                 
  6.     Written by: Dave Falkenburg
  7.     
  8.     Copyright:    © 1994-95 by Dave Falkenburg, all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.      
  12.          <1>      1/3/95    DRF        First checked in.
  13.  */
  14.  
  15. #include    "SortedDynamicArray.h"
  16.  
  17. //--------------------------------------------------------------------------------
  18. TSortedDynamicArray::TSortedDynamicArray()
  19. {
  20. }
  21.  
  22.  
  23. //--------------------------------------------------------------------------------
  24. //    An O(n) (insertion sort) routine for adding elements
  25. OSErr TSortedDynamicArray::Add(ArrayElementPtr newElement)
  26. {
  27.     ArrayElementIndex    index;
  28.  
  29.     for (index = 0;index < fElementCount;index++)
  30.     {
  31.         if (this->Compare(newElement,(*fStorage)[index]) > 0)
  32.             continue;
  33.  
  34.         return this->Insert(newElement,index);
  35.     }
  36.  
  37.     return this->InsertLast(newElement);
  38. }
  39.  
  40.  
  41. //--------------------------------------------------------------------------------
  42. //    A O(lg n) (binary search) routine for finding elements
  43. ArrayElementPtr TSortedDynamicArray::Find(ArrayElementPtr prototypeElement)
  44. {
  45.     ArrayElementIndex    low,high,index;
  46.     long                value;
  47.     
  48.     low = 0;
  49.     high = fElementCount;
  50.     
  51.     while (low < high)
  52.     {
  53.         index = (low+high)/2;
  54.         value = this->Compare(prototypeElement,(*fStorage)[index]);
  55.         
  56.         if (value < 0)
  57.             high = index;                    //    element is below "high"
  58.         else if (value == 0)
  59.             return (*fStorage)[index];        //    found the element
  60.         else
  61.             low = index+1;                    //    element is above "low"
  62.     }
  63.  
  64.     return NULL;
  65. }
  66.